//
// Created by francklinson on 2021/7/22 AT 0:05.
//
#include <iostream>
#include <unordered_map>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};


class Solution {
public:
    // 回溯  + hash
    unordered_map<Node *, Node *> nodeMemory; // 旧节点到新节点的映射
    Node *copyRandomList(Node *head) {
        if (head == nullptr) return nullptr;
        if (!nodeMemory.count(head)) {
            Node *newHead = new Node(head->val);
            nodeMemory[head] = newHead;
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }
        return nodeMemory[head];
    }
};

int main() {
    return 0;
}

